﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//剑指 Offer II 053. 二叉搜索树中的中序后继❤️
// class Solution {
// public:
//     void dfs(TreeNode* root, vector<TreeNode*>&v)
//     {
//         if(root == nullptr) return;
//         dfs(root->left,v);
//         v.push_back(root);
//         dfs(root->right,v);
//     }
//     TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
//         vector<TreeNode*>v;
//         dfs(root,v);
//         TreeNode* ret = nullptr;
//         int k = 0;
//         for(int i = 0; i < v.size(); i++)
//         {
//             if(v[i] == p)
//             {
//                 k = i;
//                 break;
//             }
//         }
//         if(k + 1 < v.size())
//         {
//             ret = v[k+1];
//         }
//         return ret;
//     }
// };
class Solution {
public:
	//非递归版本
	TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
		TreeNode* successor = nullptr;
		if (p->right != nullptr) {
			successor = p->right;
			while (successor->left != nullptr) {
				successor = successor->left;
			}
			return successor;
		}
		TreeNode* node = root;
		while (node != nullptr) {
			if (node->val > p->val) {
				successor = node;
				node = node->left;
			}
			else {
				node = node->right;
			}
		}
		return successor;
	}
};

//剑指 Offer II 052. 展平二叉搜索树
// class Solution {
// public:
//     void InBST(TreeNode* root, vector<TreeNode*>&v)
//     {
//         if(root == nullptr) return;
//         InBST(root->left,v);
//         v.push_back(root);
//         InBST(root->right,v);
//     }
//     TreeNode* increasingBST(TreeNode* root) {
//         vector<TreeNode*>v;
//         InBST(root,v);
//         TreeNode* start = v[0];
//         TreeNode* cur = v[0];
//         // cout<<v.size()<<endl;
//         for(int i = 1; i < v.size(); i++)
//         {
//             cur->left = nullptr;
//             v[i]->left = nullptr;
//             v[i]->right = nullptr;//把它们的指向全部置空，再重新指向
//             cur->right = v[i];
//             cur = v[i];
//         }
//         return start;
//     }
// };

//官方题解
class Solution {
private:
	TreeNode* resNode;

public:
	void inorder(TreeNode* node) {
		if (node == nullptr) {
			return;
		}
		inorder(node->left);

		// 在中序遍历的过程中修改节点指向
		resNode->right = node;
		node->left = nullptr;
		resNode = node;

		inorder(node->right);
	}

	TreeNode* increasingBST(TreeNode* root) {
		TreeNode* dummyNode = new TreeNode(-1);
		resNode = dummyNode;
		inorder(root);
		return dummyNode->right;
	}
};

//剑指 Offer II 050. 向下的路径节点之和❤️
//前缀和+dfs深度优先搜索
class Solution {
private:
	unordered_map<long long, int> um;//key存储到该节点时累加的值，value为该累计值存在的累加的节点个数
	int res = 0;
public:
	int pathSum(TreeNode* root, int targetSum) {
		um.insert(make_pair(0, 1));
		dfs(root, 0, targetSum);
		return res;

	}
	void dfs(TreeNode* root, long long sum, int targetSum) {//有极限情况所以给long long
		if (!root)return;
		sum += root->val;
		if (um.count(sum - targetSum))res += um[sum - targetSum];
		if (um.count(sum))
		{
			um[sum]++;
		}
		else
		{
			um.insert(make_pair(sum, 1));
		}
		dfs(root->left, sum, targetSum);
		dfs(root->right, sum, targetSum);
		um[sum]--;//当该函数结束时，程序将回到节点的父节点，也就是说，
		//在函数结束之前需要将当前节点从路径中删除，
		//从根节点到当前节点累加的节点值之和也要从哈希表map中删除
	}
};